// 求子集合
// 回溯的基本格式
function findChild(arr) {
    let res = [];
    let temth = [];

    function sortInArr(temth, start) {
        res.push(temth)
        for (let i = start; i < arr.length; i++) {
            temth.push(arr[i]);
            sortInArr(temth.slice(), i + 1);
            temth.pop()
        }
    }
    sortInArr(temth, 0)
    return res;
}
// console.log(findChild([1, 2, 3]))

// 求子集2 90
// [1,2,2] 返回的子集去除重复
function findChild2(nums) {
    let n = nums.length;
    nums = nums.sort((a, b) => a - b);
    let tmpPath = [];
    let res = [];
    let backTrace = (tmpPath, start) => {
        res.push(tmpPath);
        for (let i = start; i < n; i++) {
            // i > start 代表的是同层重复, 同层重复跳过
            if (i > start && nums[i] === nums[i - 1]) continue
            tmpPath.push(nums[i]);
            backTrace(tmpPath.slice(), i + 1);
            tmpPath.pop();
        }
    }
    backTrace(tmpPath, 0);
    return res;
}
// console.log(findChild2([1,2,2]))

// 组合两数只和 40
// candidates = [10,1,2,7,6,1,5], target = 8, 总数相加为8
var combinationSum = function (candidates, target) {
    let n = candidates.length;
    let res = [];
    let tmpPath = [];
    candidates = candidates.sort((a, b) => a - b);
    let backTrace = (tmpPath, target, start) => {
        if (target == 0) {
            res.push(tmpPath);
            return;
        }
        for (let i = start; i < n; i++) {
            if (target < candidates[i]) break;
            // 同层相同不做处理，避免重复项
            if (i > start && candidates[i - 1] == candidates[i]) continue;
            tmpPath.push(candidates[i])
            backTrace(tmpPath.slice(), target - candidates[i], i + 1);
            tmpPath.pop()
        }
    }
    backTrace(tmpPath, target, 0);
    return res;
}
// console.log("求和", combinationSum([10, 1, 2, 7, 6, 1, 5], 8))

// 生成（） 22
// 就是深度优先遍历先保证left 再处理right 最后符合要求的的放入
var generateParent = function (n) {
    let res = [];
    const help = (cur, left, right) => {
        if (cur.length == 2 * n) {
            res.push(cur);
            return;
        }
        if (left < n) {
            help(cur + "(", left + 1, right);
        }
        if (right < left) {
            help(cur + ")", left, right + 1);
        }
    }
    help("", 0, 0);
    return res;
}


// 最大公共前缀
/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    if(strs === null || strs.length === 0) {
        return ""
    }
    return twoStr(strs)

    // 求 str1 与 str2 的最长公共前缀
    function twoCommonStr(str1,str2) {
        let i = 0;
        for(;i<str1.length && i<str2.length;i++){
            if(str1.charAt(i) !== str2.charAt(i)){
                break
            }
        }
        return str1.substring(0,i)
    }  

    // 分裂两个数组长度为1
    function twoStr(arr){
        let length = arr.length
        if(length === 1){
            return arr[0]
        }
        let mid = Math.floor(length/2)
        let left = arr.slice(0,mid)
        let right = arr.slice(mid,length)
        return twoCommonStr(twoStr(left),twoStr(right))  //获取两个最长公共子串的长度
    }

};

// n皇后问题（hard 放弃）
// 逆序数 （hard 放弃）